//题目 014：最长的考拉兹序列
//        以下迭代序列定义在整数集合上：
//        n → n/2 (当 n 是偶数时)
//        n → 3n + 1 (当 n 是奇数时)
//        应用以上规则，并且以数字 13 开始，我们得到以下序列：
//        13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1
//        可以看出这个以 13 开始以 1 结束的序列包含 10 个项。虽然还没有被证明（Collatz 问
//        题），但是人们认为在这个规则下，以任何数字开始都会以 1 结束。
//        以哪个不超过 100 万的数字开始，能给得到最长的序列？
//        注意: 一旦序列开始之后，也就是从第二项开始，项是可以超过 100 万的。
//        答案：837799

import java.math.BigInteger;

public class Week014 {
    //    static void run(){
//        int n = 1000000;
//        BigInteger Three = new BigInteger("3");
//        BigInteger Ans = BigInteger.valueOf(1);
//        int AnsCnt = 1;
//        for (int i = 2; i < n; ++i) {
//            int cnt = 1;
//            BigInteger cur = BigInteger.valueOf(i);
//            while (!cur.equals(BigInteger.ONE)) {
//                ++cnt;
//                if (cur.and(BigInteger.ONE).equals(BigInteger.ZERO)) {
//                    cur = cur.shiftRight(1);
////                    cur = cur.divide(BigInteger.TWO);
//                } else {
//                    cur = cur.multiply(Three).add(BigInteger.ONE);
//                }
//            }
//            if (cnt > AnsCnt) {
//                AnsCnt = cnt;
//                Ans = BigInteger.valueOf(i);
//            }
//        }
//        System.out.println(Ans);
//    }
    static void run() {

        int n = 1000000;
        int AnsCnt = 0;
        int ans = 1;
        for (int i = 2; i < n; ++i) {
            long cur = i;
            int cnt = 0;
            while (cur != 1) {
                ++cnt;
                //&1等于%2
                //>>1等于除2
                if ((cur & 1) == 0) cur >>= 1;
                else cur = cur * 3 + 1;
            }
            if (cnt > AnsCnt) {
                AnsCnt = cnt;
                ans = i;
            }
        }
        System.out.println(ans);
    }

    public static void main(String[] args) {
        long startTime = System.nanoTime();
        run();
        System.out.println("\n程序运行时间：" + (System.nanoTime() - startTime) + "ns.");
    }
}
